Le equazioni diofantee sono equazioni in Z, o, che è lo stesso, di esse, si cercano solo le soluzioni intere, qualora non ci siano soluzioni intere l'equazione diofantea non ha soluzione, il nome viene dal matematico Diofanto vissuto nel secondo secolo e che per primo si è occupato di tali problemi.

Ci occupiamo delle equazioni lineari in due incognite del tipo

L'equazione ha soluzione se MCD(a,b) è un divisore di c. Per esempio l'equazione 10 x + 5 y =1 non ha soluzioni perché a primo membro avremo, per ogni valore di x e y, un multiplo di cinque che non può essere naturalmente 1.

L'equazione 10 x + 5y = 25 può essere semplificata in 2 x + y = 5 che può essere risolta col metodo seguente e che ricalca il procedimento euclideo per la determinazione del MCD.

Si passa dall'equazione data ad un'altra che si ottiene dividendo il maggiore per il minore tra a e b e sostituendo il maggiore con il resto della divisone. Si procede in questo modo fino a che uno dei due coefficienti a e b diventa un divisore di c, ( che avviene perché si è supposto che MCD(a,b) divida c.

si pone l'altra incognita uguale a zero, si risolve rispetto alla soluzione non nulla, si pone la soluzione trovata nell'equazione precedente si risolve rispetto all'altra incognita, e procedendo a ritroso si giunge all'equazione di partenza .

Procediamo con un esempio:

125 x + 147 y =13 147: 125= 1 resto = 22

125 x + 22 y = 13 125: 22= 5 resto = 15

15 x + 22 y =13 22:15 =1 resto = 7

15 x + 7 y =13 15 : 7 = 2 resto = 1

1 x + 7 y =13

si pone y = 0 e risolvendo si trova x=13

sostituendo x=13 in 15 x + 7 y =13 si ottiene y=-26

sostituendo y=-26 in 15 x + 22 y =13 si ottiene x=39

sostituendo x=39 in 125 x + 22 y =13 so ottiene y=-221

sostituendo y=-221 in 125 x + 147 y =13 si ottiene x=260

la soluzione base dell'equazione data è : x = 260, y = -221

le altre soluzioni sono: x = 260 + k * 147 y = -221 -k*125 con k intero.

è facile provare che se x,y è una soluzione dell'equazione ax+by = c anche

x+kb, y-ka è soluzione.

Per provare la validità dell'algoritmo descritto si parta dall'ultima equazione e si sostituisca 1 con 15-7*2

(15-7*2) 13 + 7 *0 =13

diventa

15*13 +7 * (-26) =13

si sostituisce 7 con 22-15 si ha:

15*13 +(22-15)*(-26) =13 da cui

15* 39 +22*(-26) =13

si sostituisce 15 con 125 - 22*5

(125-22*5)*39 +22*(-26)=13

125*39 +22* (-221)=13

si sostituisce 22 con 147-125

125*39+(147-125)*(-221) =13

125*260+147*(-221)=13

Si verificare facilmente che l'equazione 10 x + 5 y =1 non ha soluzione

Infatti procedendo come sopra si ha 10 : 5 = 2 resto 0 da cui si passerebbe all'equazione

5y=1 che manifestamente non ha soluzione in Z.

Caso a più incognite:

Si procede in modo analogo dividendo per il minore dei coefficienti e sostituendo con il resto.

Esempio:

12 x +45 y + 20 z =3 45=12*3+9 20=12+8

12 x + 9 y + 8 z =3 12= 8*1+ 4 9= 8*1+1
4 x + 1 y + 8 z =3 si sceglie al soluzione x=0, y=3, z=0 e si procede a ritroso

ottenendo x=0, y=3, z= -3

e infine x=6, y=3,z=-3 che è la soluzione base.

Le altre soluzioni si trovano:

x= 6 + 45*20 *k

y= 3 + 12*20 *h

z= -3 + 12*45* j

dove k + h + j =0